﻿using System;
using System.Windows.Forms;

namespace CheckPrimeNumber
{
	public partial class FrmCheckPrime : Form
	{
		private int iTimeToCheck = 10; //10

		public FrmCheckPrime()
		{
			InitializeComponent();
		}

		// Is data input a number or string?
		private bool CheckNumber( string sNumber)
		{
			bool bResult = false;
			int iCount = sNumber.Length;
			int index = 0;
			
			while( sNumber[index] >= '0' && sNumber[index] <= '9')
			{
				index++;
			}

			if (index == iCount) bResult = true;

			return bResult;
		}

		private void btnCheckPrimeNumber_Click(object sender, EventArgs e)
		{

			// Miller - Rabbin check
			// http://123doc.vn/document/19067-xay-dung-chuong-trinh-kiem-tra-so-nguyen-to-bang-thuat-toan-miller-rabin-doc-doc.htm?page=4

			//Input: n > 2, an odd integer to be tested for primality;
			//       k, a parameter that determines the accuracy of the test
			//Output: composite if n is composite, otherwise probably prime
			//write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
			//LOOP: repeat k times:
			//   pick a randomly in the range [2, n − 1]
			//   x ← ad mod n
			//   if x = 1 or x = n − 1 then do next LOOP
			//   for r = 1 .. s − 1
			//      x ← x2 mod n
			//      if x = 1 then return composite
			//      if x = n − 1 then do next LOOP
			//   return composite
			//return probably prime


			if ( CheckNumber( tbPrimeNumber.Text)) 
			{

			}
		}

		// Phan tich n thanh 
	}


	public static class RabinMiller
	{
		public static bool IsPrime(int n, int k)
		{
			if (n < 2)
			{
				return false;
			}
			if (n != 2 && n % 2 == 0)
			{
				return false;
			}
			int s = n - 1;
			while (s % 2 == 0)
			{
				s >>= 1;
			}
			Random r = new Random();
			for (int i = 0; i < k; i++)
			{
				double a = r.Next((int)n - 1) + 1;
				int temp = s;
				int mod = (int)Math.Pow(a, (double)temp) % n;
				while (temp != n - 1 && mod != 1 && mod != n - 1)
				{
					mod = (mod * mod) % n;
					temp = temp * 2;
				}
				if (mod != n - 1 && temp % 2 == 0)
				{
					return false;
				}
			}
			return true;
		}
	}
}
